package Back;

/**
 * @author zhang kun
 * @Classname Test_Back
 * @Description TODO
 * @Date 2021/8/21 15:54
 */
public class Test_Back {
    public static void main(String[] args) {
        int[] w = {1, 3, 4};
        int[] value = {15, 20, 30};
        Test_Back t = new Test_Back();
        int pack = t.pack(w, value, 4);
        System.out.println(pack);

    }

    public static int pack(int[] weight, int[] value, int n) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= weight.length; i++) {
            for (int j = n; j >= weight[i-1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
            }
        }
//
//        for(int i = 1;i<=m;i++){
//            for(int j = 0;j<=n;j++){
//                if(j - weight[i-1] >= 0){
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]] + value[i-1]);
//                }else{
//                    dp[i][j] = dp[i-1][j];
//                }
//            }
//        }
        return dp[n];

    }
}